import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 三石
 * Date: 2022-10-08
 * Time: 19:36
 */
public class MyBinaryTree {

        static class TreeNode {
            public char val;
            public TreeNode left;//左孩子的引用
            public TreeNode right;//右孩子的引用

            public TreeNode(char val) {
                this.val = val;
            }
        }


        /**
         * 创建一棵二叉树 返回这棵树的根节点
         *
         * @return
         */
        public TreeNode createTree() {
                TreeNode A = new TreeNode('1');
                TreeNode B = new TreeNode('2');
                TreeNode C = new TreeNode('3');
                TreeNode D = new TreeNode('4');

                TreeNode root=A;
                A.left = B;
                A.right = C;
                B.left = D;
                return A;
        }

        // 前序遍历
        public void preOrder(TreeNode root) {
                if (root==null) return; //如果根节点为null，不用打印
                System.out.print(root.val+" "); //打印根节点，然后依次遍历左右子树
                preOrder(root.left);
                preOrder(root.right);
        }

        // 中序遍历
        void inOrder(TreeNode root) {
                if (root==null) return;
                inOrder(root.left);
                System.out.print(root.val+" ");
                inOrder(root.right);
        }

        // 后序遍历
        void postOrder(TreeNode root) {
                if (root==null) return;
                inOrder(root.left);
                inOrder(root.right);
                System.out.print(root.val+" ");
        }

        public static int nodeSize=0;

        /**
         * 获取树中节点的个数：遍历思路
         */
        int size(TreeNode root) {
                if (root==null) return 0;
                return size(root.left)+size(root.right)+1;
        }

        /**
         * 获取节点的个数：子问题的思路
         *
         * @param root
         * @return
         */
        int size2(TreeNode root) {
                if (root==null) return 0;
                nodeSize++;
                size2(root.left);
                size2(root.right);
                return nodeSize;
        }


        /*
         获取叶子节点的个数：遍历思路
         */
        public static int leafSize = 0;

        void getLeafNodeCount1(TreeNode root) {
                if (root==null) return;
                if (root.left==null && root.right==null){
                        leafSize++;
                }
                getLeafNodeCount1(root.left);
                getLeafNodeCount1(root.right);
        }

        /*
         获取叶子节点的个数：子问题
         */
        int getLeafNodeCount2(TreeNode root) {
                if (root==null) return 0;
                if (root.left==null && root.right==null){
                        return 1;
                }
                return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
        }

        /*
        获取第K层节点的个数
         */
        int getKLevelNodeCount(TreeNode root, int k) {
                if (root==null) return 0;
                if (k==1){
                        return 1;
                }
                return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }

        /**
         *获取二叉树的高度
         *时间复杂度：O(N)
         */
        int getHeight(TreeNode root) {
                if (root==null) return 0;
                int left=getHeight(root.left);
                int right=getHeight(root.right);
                return left>right?left+1:right+1;
        }

        // 检测值为value的元素是否存在
        TreeNode find(TreeNode root, char val) {
                if (root==null)  return null;
                if (root.val==val){
                        return root;
                }
                TreeNode ret1 = find(root.left,val);
                if(ret1 != null) {
                        return ret1;
                }
                TreeNode ret2 = find(root.right,val);
                if(ret2 != null) {
                        return ret2;
                }
                return null;
        }

        /**
         * //层序遍历
         * @param root
         */
        void levelOrder(TreeNode root) {
                if(root == null) return;

                //实例化一个队列
                Queue<TreeNode> queue = new LinkedList<>();
                queue.offer(root); //并且把root节点放入队列中
                while (!queue.isEmpty()) { //队列不为空的时候
                        TreeNode cur = queue.poll();  //用cur保存队列弹出来的节点元素
                        System.out.print(cur.val+" "); //并打印
                        if(cur.left != null) {   //如果该节点的左子树不为空
                                queue.offer(cur.left); //则把左子树入列队
                        }
                        if(cur.right != null) {
                                queue.offer(cur.right);
                        }
                }
                System.out.println();
        }


        /**
         *  判断一棵树是不是完全二叉树
         * @param root
         * @return
         */
        boolean isCompleteTree(TreeNode root) {
                if(root == null) return true;

                Queue<TreeNode> queue = new LinkedList<>();
                queue.offer(root);

                while (!queue.isEmpty()) {
                        TreeNode cur = queue.poll();
                        //只要不是完全二叉树，就会存在先有null进入，再有其他值，此时cur为空，下面的语句不再执行
                        //第一个while就会结束
                        if(cur != null) {
                                queue.offer(cur.left);
                                queue.offer(cur.right);
                        }else {
                                break;
                        }
                }

                while (!queue.isEmpty()) {
                        TreeNode cur = queue.peek();
                        //不完全二叉树只能出现null然后是其他值（从上到下），不可能连续出现两个null
                        if(cur != null) {
                                //只要有一个是非空则一定不是满二叉树
                                return false;
                        }else {
                                //否则需要一一检查，直到队列为空
                                queue.poll();
                        }
                }
                return true;
        }


        /**
         * 判断是不是相同的树
         */
        boolean IsSametree(TreeNode p, TreeNode q) {
                //两棵树一棵为空一棵不为空，说明不相同
                if ((p == null && q != null) || (p != null && q == null)) return false;

                //两棵树都为空也算相同
                if (p == null && q == null)     return true;

                //只要有一个节点的值不相同，就一定不同
                if(p.val!=q.val)   return false;

                //遍历左右子树
                return IsSametree(p.left,q.left)&&IsSametree(p.right,q.right);
        }

        /**
         * 判断是不是子树
         * @param root
         * @param subRoot
         * @return
         */
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
                if(root == null) return false;

                if(IsSametree(root,subRoot)) return true;
                if(isSubtree(root.left,subRoot)) return true;
                if(isSubtree(root.right,subRoot)) return true;
                return false;
        }


        /**
         * 判断是不是对称的树
         * @param root
         * @return
         */
         boolean isSymmetric(TreeNode root) {
                if(root==null) return true;
                return isSymmetricchid(root.left, root.left);
        }
        private boolean isSymmetricchid(TreeNode leftTree,TreeNode rightTree){
                 //重新定义一个方法，判断左右树是否对称
                //如果左右子树一个为空一个不为空，则一定不对称
                if(leftTree != null && rightTree == null || leftTree == null && rightTree != null){
                        return false;
                }

                //如果两个都为空，也算对称
                if(leftTree==null&&rightTree==null){
                        return true;
                }

                //只要有一个节点的值不相等，则一定不对称
                if(leftTree.val != rightTree.val){
                        return false;
                }

                //  左子树的左和右子树的右  左子树的右和右子树的左
                return  isSymmetricchid(leftTree.left,rightTree.right)&&isSymmetricchid(leftTree.right,rightTree.left);
        }

        /**
         * 二叉树的创建和遍历
         */
        public static int i = 0;
        public class Main {

                public class TreeNode {
                        public char val;
                        public TreeNode left;
                        public TreeNode right;

                        public TreeNode(char val) {
                                this.val = val;
                        }
                }
                TreeNode createTree(String s) {
                        TreeNode root = null;
                        if (s.charAt(i) != '#') {
                                root = new TreeNode(s.charAt(i));
                                i++;
                                root.left=createTree(s);
                                root.right=createTree(s);
                        } else {
                                i++;
                        }
                        return root;
                }
                 void inOrder(TreeNode root) {
                        if (root == null) return;
                        inOrder(root.left);
                        System.out.print(root.val + " ");
                        inOrder(root.right);
                }
                public void main(String[] args) {
                        Scanner scan = new Scanner(System.in);
                        while(scan.hasNextLine()){
                                String s = scan.nextLine();
                                Main main=new Main();
                                TreeNode root=main.createTree(s);
                                inOrder(root);
                        }
                }
        }

        /**
         * 反转二叉树
         */
        public static void main(String[] args) {
                class Solution {
                        public TreeNode invertTree(TreeNode root) {
                                if (root == null) {
                                        return null;
                                }
                                TreeNode left = invertTree(root.left);
                                TreeNode right = invertTree(root.right);
                                root.left = right;
                                root.right = left;
                                return root;
                        }
                }
        }
}
